package project2;

/*
* 2019-11-23 快速排序
* 切分
* */
public class RQ {
    public void sort(int[] a){
        sort(a,0,a.length-1);
    }

    private void sort(int[] a, int lo, int hi) {
        if(hi <= lo) return;
        int j = partion(a,lo,hi);//切分
        sort(a, lo, j-1);
        sort(a,j+1, hi);
    }

    public int partion(int[] a, int lo, int hi){
        int i = lo, j = hi+1;
        int v = a[lo];
        while (true){
            //把比v小的都放左边，比v大的都放在右边
            while (a[++i] < v) if(i == hi) break;//这里是大于等于
            while (a[--j] > v);//当j减到lo的时候，必然不会大于v会直接退出
            if(i>=j) break;
            exch(a,i,j);
        }
        exch(a,lo,j);
        return j;
    }

    private void exch(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}
